package com.leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * 你可以按 任何顺序 返回答案。
 * 示例 1：
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 * 示例 2：
 * 输入：n = 1, k = 1
 * 输出：[[1]]
 * 提示：
 * 1 <= n <= 20
 * 1 <= k <= n
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combinations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年11月22日 10:58
 */
class Code77 {
    public static void main(String[] args) {
        Code77 code = new Code77();
        List<List<Integer>> combine = code.combine(4, 2);
        System.out.println(combine);
    }
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        way(1,k,n);
        return list;
    }
    public void way(int num,int k,int n){
        if(temp.size() + (n-num+1) < k){
            return;
        }
        if(temp.size() == k){
            list.add(new ArrayList<>(temp));
            return;
        }
        for(int i = num;i<=n;i++){
            temp.add(i);
            way(i+1,k,n);
            temp.remove(temp.size()-1);
        }
    }

    /**
     * 官方题解
     * @author ymy
     * @date 2021/11/22 11:44
     * @return null
     */
    public List<List<Integer>> combine1(int n, int k) {
        dfs(1, n, k);
        return list;
    }
    public void dfs(int cur, int n, int k) {
        // 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.size() == k) {
            list.add(new ArrayList<Integer>(temp));
            return;
        }
        // 考虑选择当前位置
        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
}
